/*https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/description/
600.不含连续1的非负整数
medium, 方钊堉 2024.10.07
数位DP*/


class Solution {
private:
    int memo[32][2]; // 记忆化数组

public:
    int findIntegers(int n) {
        vector<int> binaryDigits;
        bool leadingBitFound = false;
        // 将数字n转换为二进制形式
        for (int i = 30; i >= 0; --i) {
            if (n & (1 << i)) {
                if (!leadingBitFound) leadingBitFound = true;
                binaryDigits.push_back(1);
            } else {
                if (leadingBitFound) binaryDigits.push_back(0);
            }
        }
        memset(memo, -1, sizeof(memo));
        return dfs(0, 0, true, binaryDigits);
    }

    int dfs(int position, int previousBit, bool isLimited, vector<int>& binaryDigits) {
        if (position == binaryDigits.size()) return 1;
        if (!isLimited && memo[position][previousBit] != -1) return memo[position][previousBit]; // 记忆化
        int upperBound = isLimited ? binaryDigits[position] : 1; // 根据是否受限确定当前位的上限
        int result = 0;
        for (int currentBit = 0; currentBit <= upperBound; ++currentBit) {
            if (previousBit == 1 && currentBit == 1) continue; // 连续1不转移状态
            result += dfs(position + 1, currentBit, isLimited && currentBit == upperBound, binaryDigits);
        }
        if (!isLimited) memo[position][previousBit] = result;
        return result;
    }
};